package DoExercise.JianzhiOffer;

/**
 * 输入一个链表，输出该链表中倒数第k个结点。
 * 如果该链表长度小于k，请返回空。
 * <p>
 * {1,2,3,4,5},1
 * <p>
 * {5}
 * <p>
 * https://www.nowcoder.com/practice/886370fe658f41b498d40fb34ae76ff9?tpId=13&&tqId=11167&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
 */
public class Offer082_链表中倒数最后k个结点
{

    public static void main(String[] args)
    {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        Offer000_Common.ListNode head = Offer000_Common.deserialize_ListNode(arr);
        Offer000_Common.printListNode(head);
        System.out.println();
        Offer000_Common.ListNode ans = FindKthToTail(head, 7);
        Offer000_Common.printListNode(ans);
    }

    /**
     * 大小指针/双指针，可实现功能
     * <p>
     * 一个指针先走K步，另一个从头开始，当第一个指针走到头时，第二个指针所指的位置就是所求的位置。
     *
     * @param pHead
     * @param k
     * @return
     */
    public static Offer000_Common.ListNode FindKthToTail(Offer000_Common.ListNode pHead, int k)
    {
        if (pHead == null)
        {
            return null;
        }
        Offer000_Common.ListNode fast = pHead;//先走
        Offer000_Common.ListNode slow = pHead;//后走

        while (k > 0 && fast != null)
        {
            k--;
            fast = fast.next;
        }

        if (k != 0) return null;

        while (fast != null)
        {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }


}
